#include<iostream>

using namespace std;

int main()
{
    int T;cin>>T;
    while(T--)
    {
        int n;cin>>n;
        long long res=n;
        for(int i=2;i<=n/i;++i)
        {
            if(n%i==0)
            {
                res=res/i*(i-1);
                while(n%i==0) n/=i;
            }
        }
        if(n>1) res=res/n*(n-1);
        cout<<res<<endl;
    }
   
    return 0;
}